package 中等.贪心思想;

import java.util.PriorityQueue;

/**
 * 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。
 * 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提
 * 前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
 * 给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们
 * 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一
 * 个班级，使得 所有 班级的 平均 通过率 最大 。
 * 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平
 * 均通过率 是所有班级的通过率之和除以班级数目。
 * 请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与
 * 标准答案误差范围在 10-5 以内的结果都会视为正确结果。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-average-pass-ratio
 */
public class 最大平均通过率_1792 {

    public static void main(String[] args) {

        System.out.println(maxAverageRatio(new int[][]{{1, 2}, {3, 5}, {2, 2}}, 2));

    }

    /**
     * 优先队列+贪心
     * 将所有班级按照 加上一个通过人数的通过率-当前通过率 的差值从大到小排序
     * 每次选择差值最大的，也就是可以提高的最大通过率的班级，将通过人数和总
     * 人数+1
     */
    public static double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> {
            double curA = (double) a[0] / a[1];
            double afterA = (double) (a[0] + 1) / (a[1] + 1);
            double curB = (double) b[0] / b[1];
            double afterB = (double) (b[0] + 1) / (b[1] + 1);
            return afterB - curB - (afterA - curA) > 0 ? 1 : -1;
        });

        for (int[] aClass : classes) {
            priorityQueue.add(aClass);
        }
        while (extraStudents-- > 0) {
            int[] poll = priorityQueue.poll();
            poll[0]++;
            poll[1]++;
            priorityQueue.add(poll);
        }
        double sumAvg = 0;
        int size = priorityQueue.size();
        while (!priorityQueue.isEmpty()) {
            int[] poll = priorityQueue.poll();
            sumAvg += (double) poll[0] / poll[1];
        }
        return sumAvg / size;
    }

}
